package ink.lovejinhu.swardToOffer;

/**
 * @author jinhu
 * created 2021-08-16 10:18
 */
public class Offer_042 {
    /**
     * 设以i位置结尾的连续最大子数组和为f(i)
     * f(i)=f(i-1)+nums[i],nums[i]
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int[] ints = new int[nums.length];
        ints[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            ints[i] = Math.max(ints[i - 1] + nums[i], nums[i]);   //可用滚动数组优化
            if (ints[i] > max) {
                max = ints[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Offer_042 offer_042 = new Offer_042();
        int[] temp = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int i = offer_042.maxSubArray(temp);
        System.out.println("--" + i);
    }
}
